package com.zyk.grate_offer.class01;

/**
 * 给定一个有序数组arr，代表坐落在X轴上的点
 * 给定一个正数K，代表绳子的长度
 * 返回绳子最多压中几个点？
 * 即使绳子边缘处盖住点也算盖住
 *
 * @author zhangsan
 * @date 2021/4/21 8:55
 */
public class Code01_MaximumOfPointsCovered {

    // 双指针
    public static int maxNum(int[] arr, int k) {
        int l = 0, r = 1;
        int ans = 0;

        while (r < arr.length) {
            if (arr[r] - arr[l] <= k) {
                r++;
            } else {
                ans = Math.max(ans, r - l);
                l++;
            }
        }
        ans = Math.max(ans, r - l);
        return ans;
    }

    public static int maxNum2(int[] arr, int L) {
        int res = 1;
        for (int i = 0; i < arr.length; i++) {
            int nearest = nearestIndex(arr, i, arr[i] - L);
            res = Math.max(res, i - nearest + 1);
        }
        return res;
    }

    public static int nearestIndex(int[] arr, int R, int value) {
        int L = 0;
        int index = R;
        while (L <= R) {
            int mid = L + ((R - L) >> 1);
            if (arr[mid] >= value) {
                index = mid;
                R = mid - 1;
            } else {
                L = mid + 1;
            }
        }
        return index;
    }


    // for test
    public static int[] generateArray(int maxLen) {
        int[] res = new int[maxLen];
        res[0] = (int) (Math.random() * 10);
        int range = 10;
        for (int i = 1; i < res.length; i++) {
            res[i] = (int) (res[i - 1] + Math.random() * range + 1);
        }
        return res;
    }

    // for test
    public static void main(String[] args) {
        /*int[] arr = {3, 11};
        int k = 1;
        System.out.println(maxNum(arr, k));
        System.out.println(maxNum2(arr, k));*/

        int times = 100000;
        for (int i = 1; i <= times; i++) {
            int[] arr = generateArray(i);
            int k = (int) (Math.random() * i)+ 1;
            int ans1 = maxNum(arr, k);
            int ans2 = maxNum2(arr, k);
            if(ans1 != ans2) {
                System.out.println("OOPS!");
                break;
            }
        }

    }

}
